import java.util.Random;

public class Main {
    static Random rn = new Random(System.currentTimeMillis());
    public static int getRandomInt(int i){
        return Math.abs(rn.nextInt())%i + 1;
    }

    public void test(){
        int n = getRandomInt(1000000000);

        Solution solution = new Solution();

        int expected = occurrencesOf3sInRange(n);
        int actual = solution.occurrencesOf3sInRange(n);

        if(expected != actual){
            String msg = "Test Failed\n";
            msg += "Input:" + n + "\n";
            msg += "Expected:" + expected + "\n";
            msg += "Actual:" + actual;
            throw new RuntimeException(msg);
        }
    }

    public void testSpecial(int n){
//        int n = getRandomInt(1000000000);

        Solution solution = new Solution();

        int expected = occurrencesOf3sInRange(n);
        int actual = solution.occurrencesOf3sInRange(n);

        if(expected != actual){
            String msg = "Test Failed\n";
            msg += "Input:" + n + "\n";
            msg += "Expected:" + expected + "\n";
            msg += "Actual:" + actual;
            throw new RuntimeException(msg);
        }
    }

    private String arrayToString(int[] num) {
        String ret = "[";
        for(int i=0; i<num.length; i++){
            if(i != num.length -1){
                ret += num[i] + ",";
            }else{
                ret += num[i];
            }
        }
        return ret + "]";
    }

    public static void main(String[] args) {
        try {
            Main main = new Main();
            for (int i = 0; i < 20; i++) {
                main.test();
            }
            main.testSpecial(999999);
            main.testSpecial(0);
        }catch (Exception ex){
            System.out.println(ex.getMessage());
            System.exit(-1);
        }
    }
    public int occurrencesOf3sInRange(int n) {
        if(n == 0) {
            return 0;
        }
        int digit = (int)Math.log10(n) + 1;
        int[][] dp = new int[digit+1][2];
        // dp[i][0] = numberOf2sInRange(n % pow(10, i)) 保存0~n的1-i位组成的数包含3的个数
        // dp[i][1] = numberOf2sInRange(99..9) 保存i位均为9包含3的个数
        dp[1][0] = n % 10 >= 3 ? 1:0;
        dp[1][1] = 1;
        for(int i = 2; i <= digit; i++) {
            int k = n/ ((int)Math.pow(10, i-1)) % 10;
            dp[i][0] = k * dp[i-1][1] + dp[i-1][0];
            if(k == 3) {
                dp[i][0] += n % (int)Math.pow(10, i-1) +1;
            } else if(k > 3){
                dp[i][0] +=  (int)Math.pow(10, i-1);
            }
            //计算1-i位均为9的值包含3的个数
            dp[i][1] = 10 * dp[i-1][1] + (int)Math.pow(10, i-1);
        }
        return dp[digit][0];
    }
}
